/*
 * @lc app=leetcode.cn id=463 lang=javascript
 *
 * [463] 岛屿的周长
 */

// @lc code=start
/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function (grid) {
  let result = 0;
  let m = grid.length;
  if (!m) {
    return result;
  }
  let n = grid[0].length;
  const direction = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];

  function dfs(x, y) {
    if (x < 0 || x >= m || y < 0 || y >= n || !grid[x][y]) {
      return 1;
    }

    if (grid[x][y] === -1) {
      return 0;
    }
    // 标记访问过的坐标
    grid[x][y] = -1;
    let result = 0;

    for (let k = 0; k < direction.length; k++) {
      const tx = x + direction[k][0];
      const ty = y + direction[k][1];
      result += dfs(tx, ty);
    }

    return result;
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        result += dfs(i, j);
      }
    }
  }

  return result;
};
// @lc code=end

/**
 * 时间复杂度：O(nm)，其中 n 为网格的高度，m 为网格的宽度
 * 空间复杂度：O(nm)。深度优先搜索复杂度取决于递归的栈空间，而栈空间最坏情况下会达到 O(nm)
 */
